#ifndef BTL_MATHS_RANDOMSAMPLER
#define BTL_MATHS_RANDOMSAMPLER

#include <algorithm>
#include <iterator>

namespace btl
{
namespace maths
{

/// This is like std::random_shuffle(), except that it only performs the first N steps
/// After shuffleMofN(begin, nth, end) has been called
///   begin -> nth contain a random sample taken from the original begin -> end range
///
/// ItT must be a random access iterator, and std::iter_swap<ItT>() must work
template <typename ItT, typename RNG>
void shuffleMofN(ItT it, const ItT& nth, const ItT& end, RNG& rng);

} // namespace maths
} // namespace btl

namespace btl
{
   using maths::shuffleMofN;
}

// ====================================================================
// ------ Implementation

namespace btl
{
namespace maths
{

template <typename ItT, typename RNG>
inline void shuffleMofN(ItT it, const ItT& nth, const ItT& end, RNG& rng)
{
   size_t remain = std::distance(it, end);
   while (it != nth)
   {
      size_t idx = rng(remain);
      std::iter_swap(it, it + idx);
      ++it; --remain;
   }
}

} // namespace maths
} // namespace btl

#endif // BTL_MATHS_RANDOMSAMPLER
